# 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
#  请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
#
#  示例 1：
# 输入：nums = [100,4,200,1,3,2]
# 输出：4
# 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
#
#  示例 2：
# 输入：nums = [0,3,7,2,5,8,4,6,0,1]
# 输出：9
from typing import List


class Solution:
    def longestConsecutive2(self, nums: List[int]) -> int:
        """
        解法二:hash表
        先将数组转化成Set(去重)
        然后遍历set
            方式一:
               枚举当前元素的+1,+2 ... 看set里面是否存在并更新连续序列的长度

            方式二:
               先判断当前元素 -1 在不在set里面，
               如果存在则跳过(避免重复搜索)，不在再去判断+1, +2是否存在，并更新连续序列的长度
        :param nums:
        :return:
        """
        if nums is None or len(nums) == 0:
            return 0
        setNums = set(nums)  # 使用set进行去重
        res = 1
        for num in setNums:
            if (num - 1) not in setNums:
                tmpRes = 1
                while (num + 1) in setNums:
                    num += 1
                    tmpRes += 1
                res = max(tmpRes, res)
        return res

    def longestConsecutive1(self, nums: List[int]) -> int:
        """
        解法一:去重后排序最后动态规划
        :param nums:
        :return:
        """
        if nums is None or len(nums) == 0:
            return 0
        sortedNums = list(set(nums))  # 使用set进行去重
        sortedNums.sort()
        n = len(sortedNums)
        dp = [1] * n  # dp[i] 表示以nums[i]结尾的最长数字连续序列长度
        res = 1
        for i in range(1, n):
            if sortedNums[i] - sortedNums[i - 1] == 1:
                dp[i] = dp[i - 1] + 1
                res = max(res, dp[i])
        return res

    def longestConsecutive(self, nums: List[int]) -> int:
        return self.longestConsecutive2(nums)


if __name__ == "__main__":
    nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
    # nums = [1, 2, 0, 1]
    print(Solution().longestConsecutive(nums))
